#include <cmath>
#include <sstream>
#include <pthread.h>
#include <sys/time.h>
#include <string.h>
#include "shorthand.h"

#ifndef _UTIL_H_
#define _UTIL_H_

extern pthread_mutex_t G_LOCK;

#define COMPARE_BY(a,b,x) if (a.x < b.x) return true; if (b.x < a.x) return false;

// Some constants we need
extern float OneOverRandMax;
extern float NINF;

inline uint64 Shuffle(uint64 x) { return (x >> 32) | (x  << 32); }

inline uint64 Fingerprint(uint64 x, uint64 y = 0) {
  return Shuffle(x * 0x1852389021532685ull + y * 0x4251256931465823ull);
}
inline uint64 Fingerprint(const string & s, uint64 level = 0) {
  uint64 ret = Fingerprint(s.size(), level);
  uint64 pos = 0;
  uint64 x;
  for (; pos+8 <= s.size(); pos += 8) {
    memcpy(&x, &s[pos], 8);
    ret = Fingerprint(ret, x);    
  }
  x = 0;
  memcpy(&x, &s[pos], s.size() - pos);
  ret = Fingerprint(ret, x);
  return ret;
}
template<class T>
struct PointerHash {
  size_t operator () (const T * p) const {
    return (size_t)(p);
  }
};
template <class T> 
struct SimpleHash {
  size_t operator () (const T & p) const { return (size_t) p;}
};

// pthreads
inline void Lock(pthread_mutex_t& m, const char* name = NULL) {
  //if (name) cout << "trying to lock " << name << endl;
  pthread_mutex_lock(&m);
  //if (name) cout << "locked " << name << endl;
}

inline void Unlock(pthread_mutex_t& m, const char* name = NULL) {
  //if (name) cout << "unlocking " << name << endl;
  pthread_mutex_unlock(&m);
}

// Lets you create a lock that gets garbaged via object destruction
// Takes a lock_now parameter to accomodate locks that sometimes happen
struct MutexLocker {
MutexLocker(pthread_mutex_t * lock, bool lock_now = true) :lock_(lock), locked_(false) {
  if (lock_now) Lock();
}
  void Lock() { pthread_mutex_lock(lock_); locked_ = true;}
  void Unlock() { pthread_mutex_unlock(lock_); locked_ = false;}
  // returns true on success. 
  bool TryLock() { 
    if (pthread_mutex_trylock(lock_) == 0) locked_ = true;
    return locked_;
  }
  bool IsLocked() { return locked_;}
  ~MutexLocker() { if (IsLocked()) Unlock();}
  pthread_mutex_t *lock_;
  bool locked_;
};

// A way to synchronize threads at a barrier
// First call Init, then call Pass, it will let everyone past the Pass
// once everyone has called it
struct Barrier {
  void Init(uint64 num_threads) {
    num_threads_ = num_threads;
    num_finished_ = 0;
    pthread_mutex_init(&lock_, NULL);
    pthread_cond_init(&finished_cv_, NULL);
  }
  void Pass() {
    pthread_mutex_lock(&lock_);
    num_finished_++;
    if (num_finished_ == num_threads_) {
      pthread_cond_broadcast(&finished_cv_);
      num_finished_ = 0;
    } else {
      pthread_cond_wait(&finished_cv_, &lock_);
    }
    pthread_mutex_unlock(&lock_);
  }
  pthread_cond_t finished_cv_;
  pthread_mutex_t lock_;
  uint64 num_threads_;
  uint64 num_finished_;
};

// Log space computations

// a is the ln of A, b is the ln of B
// compute ln (A + B)
float LnSum(float a, float b);

// ln version of +=
void LnSumEq(float &a, float b);

double LnFactorial(uint32 n);

// Micronat Log
extern const uint32 kLogCacheSize;
extern uint64 * LOG_CACHE;
void InitLogCache();
inline uint64 MLn(uint32 n) {
  if (n < kLogCacheSize) return LOG_CACHE[n];
  return (uint64)(log(n) * 1000000);
}

inline uint64 DMLn(double d) {
  CHECK(d > 0);
  return (uint64)(log(d) * 1000000);
}

struct RNG {
  RNG() { x_ = rand();}
  void Seed(uint64 seed) {x_ = seed;}
  uint64 Random() {
    x_ = x_ * 6364136223846793005ull + 1442695040888963407ull;
    return ( (x_ & 0xffffffff00000000ull) >> 32) 
      | ( (x_ & 0x00000000ffffffffull) << 32);
  }
  uint64 Round(double x) {
    CHECK(x >= 0.0);
    uint64 start = (uint64) x;
    double remainder = x - start;
    if (RandomFraction() < remainder) start++;
    return start;
  }

  uint64 x_;

  double RandomFraction();
  uint64 RandomImportance(uint64 external);
};

// Some randomness
// returns a random float between 0 and 1 inclusive
uint64 BitCount(uint64 x);

// vector of pairs of (i, v[i]) sorted by decreasing v[i]
vector<pair<int, float> > DecreasingSortWithIndices(const vector<float>& v);

// Work on strings
string Upcase(const string& s);

template <class A, class B>
struct GreaterSecond {
  bool operator () (const pair<A, B> &p1, const pair<A, B> &p2) {
    return (p1.second > p2.second);
  }
};
template <class A, class B>
struct LessFirst {
  bool operator () (const pair<A, B> &p1, const pair<A, B> &p2) {
    return (p1.first < p2.first);
  }
};

template <class A>
string VectorToString(const vector<A> & v) {
  ostringstream out;
  out << "(";
  for (uint32 i=0; i<v.size(); i++) { 
    if (i>0) out << " ";
    out << v[i];
  }
  out << ")";
  return out.str();
}

struct StableVectorException {
  StableVectorException(void *v) :vector_(v) {}
  StableVectorException(const StableVectorException & o) :vector_(o.vector_){}
  void *vector_;
};

// a fixed capacity vector that does not move in memory
template<class A> struct StableVector {
  StableVector(uint64 capacity) {
    capacity_ = capacity;
    current_ = data_ = new A[capacity_];
    limit_ = data_ + capacity_;
    descriptor_ = "unknown";
  }
  ~StableVector() {
    delete [] data_;
  }
  int64 size() {  return current_ - data_; }
  A & operator [](int i) { return data_[i];}
  const A & operator [] (int i) const { return data_[i];}
  void extend() { current_++;}
  void push_back() {
    if (current_ >= limit_) {
      cout << "Stable vector exception on " << descriptor_ << endl;
      throw StableVectorException((void *)this);
    }
    current_++;
  }
  void push_back(const A & a) { 
    push_back();
    back() = a; 
  }

  void pop_back() {/*CHECK(current_ > data_);*/ current_--;}
  void clear() {current_ = data_;}
  void resize(uint64 new_size) { current_ = data_ + new_size; }
  void RelativeResize(int64 delta) { current_ += delta;}
  A & back() { return current_[-1]; }
  A * begin() { return data_;}
  A * end() { return current_;}
  bool NearCapacity(uint64 margin) { return (current_ + margin >= limit_); }

  A *current_;
  A *data_;
  A *limit_;
  uint64 capacity_;
  const char * descriptor_;
};

// increments an int on construction and decrements it on destruction
struct Increment { 
  Increment(int *target) :target_(target) {(*target_)++;}
  ~Increment() {(*target_)--;}
  int * target_;
};

int UltimateDestination(const map<int, int> & m, int source);

void ResetMilli();
void PrintElapsedTime();
void PrintElapsedTime2();
int GetMilliCount();

// Putting a string back on an istream
void putback(istream & in, string s);

string ReadLine(istream & in);

// Reading a file or a stream into memory?
void ReadIntoString(string * res, istream & in);
void ReadFileIntoString(string * res, string filename);

// Todo
bool IsSafeFileName(string filename);

// MMapping a file
// Returns results in the passed in parameters
bool Mmap (string filename, uchar ** block, int64 * length);

inline int HexToInt(const string &h) {
  istringstream in(h);
  int ret;
  in >> hex >> ret;
  return ret;
}

// For reading and writing raw binary data using strings as
// intermediate representations.

template <class T> T ReadType(const char ** source) {
  T ret;
  memcpy(&ret, *source, sizeof(T));
  *source += sizeof(T);
  return ret;
} 

template<class T> string RawString(const T & t) {
  return string((const char *)&t, sizeof(T));
}

string itoa(int i);

// Predicate takes an int64.
// It is assumed that predicate returns false for all values less than an unknown
//  x and true for all values greater than or equal to x. 
//  It is assumed that low <= x <= high
//  Returns x.
template <class Predicate> 
int64 FirstSatisfaction(int64 low, int64 high, Predicate & predicate) {
  if (low == high) return low;
  int64 mid = low + (high - low) / 2;
  bool result = predicate(mid);
  if (result) return FirstSatisfaction(low, mid, predicate);
  return FirstSatisfaction(mid+1, high, predicate);
}

// compute k^n mod 2^32
uint64 UInt64Pow(uint64 k, uint64 n);

// a stack where the bottom falls out automatically when the stack grows too big
template<class T> struct BottomlessStack {
  BottomlessStack(uint64 size) {
    size_ = size;
    data_ = new T[size_];
    clear();
  }
  ~BottomlessStack() {
    delete [] data_;
  }
  void clear() {
    bottom_ = top_ = 0;
    bottom_lost_ = false;
  }
  uint64 depth() {
    return (top_ + size_ - bottom_) % size_;
  }
  void push(const T & t) {
    if (depth() + 1 == size_) {
      bottom_ = (bottom_ + 1) % size_;
      bottom_lost_ = true;
    }
    data_[top_] = t;
    top_ = (top_ + 1) % size_;
  }
  void pop() {
    CHECK(depth() > 0);
    top_ = (top_ + size_ - 1) % size_;
  }
  T & top() {
    return data_[(top_ + size_ - 1) % size_];
  }

  T * data_;
  uint64 bottom_;
  uint64 top_;
  uint64 size_;
  bool bottom_lost_;
};

inline int64 PortableTime() {
  struct timeval tm;
  gettimeofday(&tm, NULL);
  return (uint64)tm.tv_sec * 1000000 + tm.tv_usec;
}

inline uint64 ShardBegin(uint64 total, uint64 num_shards, uint64 shard_num) {
  return shard_num * total / num_shards;
}

inline uint64 ShardEnd(uint64 total, uint64 num_shards, uint64 shard_num) {
  return (1 + shard_num) * total / num_shards;
}

// returns the least multiple of b greater than or equal to a
inline uint64 RoundUpToMultipleOf(uint64 a, uint64 b) {
  return ((a-1)/b +1) * b;
}

inline void ProbabilisticIncrementFloat(float *target, float increment, RNG *rng) {
  float min_increment = *target * 0.1;
  if (increment < min_increment) {
    if (rng->RandomFraction() < increment / min_increment) 
      increment = min_increment;
    else return;
  }
  while (1) {
    float old_val = *target;
    float new_val = old_val + increment;
    if (__sync_bool_compare_and_swap((uint32 *)target, *((uint32 *)&old_val), 
				     *((uint32*)(&new_val)))) return;
  }
}

#endif
